`
https://leetcode.cn/problems/path-with-maximum-probability/
`

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[]} succProb
 * @param {number} start_node
 * @param {number} end_node
 * @return {number}
 */
var maxProbability = function (n, edges, succProb, start_node, end_node) {
  const graph = Array.from({ length: n }, () => [])
  for (let i = 0; i < edges.length; i++) {
    const [from, to] = edges[i]
    const prob = succProb[i]
    // 无向图就是双向图
    graph[from].push([to, prob])
    graph[to].push([from, prob])
  }
  const distTo = new Array(n).fill(-1)
  distTo[start_node] = 1
  const pq = new Heap((a, b) => b.probFromStart - a.probFromStart)
  pq.push(new State(start_node, 1))

  while (!pq.isEmpty()) {
    const { node: curNode, probFromStart: curProb } = pq.pop()

    // 第一次到达终点就是最大概率路径
    if (curNode === end_node) return curProb

    for (const [nextNode, prob] of graph[curNode]) {
      const nextProb = curProb * prob
      // 新概率比之前的概率更大才更新，入队新节点
      if (nextProb > distTo[nextNode]) {
        distTo[nextNode] = nextProb
        pq.push(new State(nextNode, nextProb))
      }
    }
  }

  return 0
};

class State {
  constructor(node, probFromStart) {
    this.node = node
    this.probFromStart = probFromStart
  }
}